Linear Search vs. Binary Search

Interactive algorithm analysis & benchmarking — generated by algoscope

Notes

Comparison on uniformly increasing integer arrays with random targets.

Beginner Summary

linear_search

When the input size n doubles, the runtime grows by approximately 1.89×, which suggests performance closer to O(n).

insights
binary_search

When the input size n doubles, the runtime grows by approximately 1.08×, which suggests performance closer to O(log n).

insights

Interview Summary

linear_search
Quick

linear_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

binary_search
Quick

binary_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

Quick Stats

memory
6
Input sizes (n)
timer
6 runs
Measured points

Use the tabs below to explore charts, memory, comparisons, and method details.

Manual Big-O Analysis

linear_search
Static analysis of `linear_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: no **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.
binary_search
Static analysis of `binary_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: yes **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.

Beginner & Interview Summaries

linear_search

When the input size n doubles, the runtime grows by approximately 1.89×, which suggests performance closer to O(n).

Interview: linear_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

binary_search

When the input size n doubles, the runtime grows by approximately 1.08×, which suggests performance closer to O(log n).

Interview: binary_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

Runtime Chart

Runtime Table (mean ± 95% CI)

n linear_search binary_search
1000 15.27 µs ± 5.88 µs 1.74 µs ± 139.94 ns
2000 29.49 µs ± 12.97 µs 1.91 µs ± 109.11 ns
4000 53.80 µs ± 20.77 µs 2.38 µs ± 298.79 ns
8000 151.18 µs ± 33.37 µs 2.28 µs ± 126.90 ns
16000 234.90 µs ± 76.87 µs 2.35 µs ± 147.68 ns
32000 311.75 µs ± 92.81 µs 2.47 µs ± 185.25 ns

Peak Memory Chart

Memory Table (mean ± 95% CI)

n linear_search binary_search
1000 226.91 B ± 11.34 B 176.00 B ± 0.00 B
2000 226.91 B ± 11.34 B 188.73 B ± 9.82 B
4000 232.00 B ± 0.00 B 204.00 B ± 0.00 B
8000 232.00 B ± 0.00 B 204.00 B ± 0.00 B
16000 232.00 B ± 0.00 B 204.00 B ± 0.00 B
32000 232.00 B ± 0.00 B 204.00 B ± 0.00 B

Comparison Summary

Best/worst runtime at each n (lower is better). Mean ranks summarize performance across all n.

n Best Runtime Worst Runtime Mean Ranks
1000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
2000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
4000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
8000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
16000 binary_search linear_search linear_search: 2.00 binary_search: 1.00
32000 binary_search linear_search linear_search: 2.00 binary_search: 1.00

Mean Runtime Comparison (bar)

Bar chart placeholder: you can render an additional Plotly bar chart here comparing means per function.

Methods & Notes

Methods: - **Runtime** measured with `time.perf_counter()`; each (function, n) pair ran 11 times after 2 warmup iterations. GC was enabled and collected before runs. - **Memory** peak measured with `tracemalloc` backend (`tracemalloc` by default). - **Confidence Intervals:** T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed. - **Reference curves** (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.